package com.fineaiops.gateway.util;

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;

public class LCSUtil
{
    public static void main(String[] args)
    {
        //保留空字符串是为了getLength()方法的完整性也可以不保留
        //但是在getLength()方法里面必须额外的初始化c[][]第一个行第一列
        String[] x = "hi empty error message".split(" ");
        String[] y = "hello empty error message".split(" ");
        System.out.println(LCS(x,y));
//        int[][] b = getLength(x, y);
//        Display(b, x, x.length-1, y.length-1);
    }
    /**
     * @param x
     * @param y
     * @return 返回一个记录决定搜索的方向的数组
     */
    public static String LCS(String[] x, String[] y)
    {
        int[][] b = new int[x.length][y.length];
        int[][] c = new int[x.length+1][y.length+1];
        for(int i=1; i<=x.length; i++)
        {
            for(int j=1; j<=y.length; j++)
            {
                //对应第一个性质
                if(Objects.equals(x[i-1], y[j-1]))
                {
                    c[i][j] = c[i-1][j-1] + 1;
                    b[i-1][j-1] = 1;
                }
                //对应第二或者第三个性质
                else if(c[i-1][j] >= c[i][j-1])
                {
                    c[i][j] = c[i-1][j];
                    b[i-1][j-1] = 0;
                }
                //对应第二或者第三个性质
                else
                {
                    c[i][j] = c[i][j-1];
                    b[i-1][j-1] = -1;
                }
            }
        }
        System.out.println(c[x.length][y.length]);
        List<String> strList = new ArrayList<>();
        Display(b, x, x.length-1, y.length-1, strList);
        StringBuilder builder = new StringBuilder();
        for (String str: strList) {
            builder.append(str).append(" ");
        }
        if (builder.length() > 0) {
            builder.deleteCharAt(builder.length()-1);
        }

        return builder.toString();
    }
    //回溯的基本实现，采取递归的方式
    // todo 改循环
    public static void Display(int[][] b, String[] x, int i, int j, List<String> strList)
    {
        if(i < 0 || j < 0)
            return;
        if(b[i][j] == 1)
        {
            Display(b, x, i-1, j-1, strList);
            strList.add(x[i]);
        }
        else if(b[i][j] == 0)
        {
            Display(b, x, i-1, j, strList);
            if(strList.size()==0 || !strList.get(strList.size() - 1).equals("*")) {
                strList.add("*");
            }

        }
        else if(b[i][j] == -1)
        {
            Display(b, x, i, j-1, strList);
            if(strList.size()==0 || !strList.get(strList.size() - 1).equals("*")) {
                strList.add("*");
            }
        }
    }
}
